The present invention relates to an information processing method, and in particular, to an apparatus and method for optimal placement of components.
Conventionally, computers are used for determining the placement of components on a printed circuit board as described in, for example, Published Unexamined Application No. 09-181185. However, when the number of components is large or the correlation between components is complicated, the optimality of local component placement can affect the result of conventional methods, thus the computers often output, as an optimal value, a placement value that is lower than the optimal value.
As shown in FIG. 2, there are the following constraints in designing an integrated circuit (IC) 103:
(1) 16 or 32 pins 105 of the same size are provided,
(2) the printed substrate by necessity has a connector 111 and the connector 111 also has pins,
(3) connections between the IC pins 105 or between the IC pins 105 and the pins of connector 111 are determined by the logical design of the printed circuit board,
(4) both of the top and back sides of the printed circuit board substrate are used for wiring 107 with only vertical wiring being printed on the top side and horizontal wiring on the back side,
(5) a hole through the substrate is bored for wiring from the top side to the back side (or vice versa), and
(6) conductors for wiring 107 are required to be spaced at a certain distance or over.
If components cannot be interconnected by wiring on the printed substrate, the substrate is fabricated without that wiring and the components are directly interconnected by soldering a conductor in a separate process (this connection is called the xe2x80x9cjumperxe2x80x9d). Since the manufacturing process increases by adding a jumper 109, the cost increases correspondingly. In addition, there occurs a problem that some wiring cannot be printed if the wiring is not proper.
It is an object of the present invention to provide component placement which reduces computational complexity as much as possible and provides a high evaluation value.
It is another object of the present invention to provide a system for determining the placement of components that provides a high evaluation value independently of the platform of a system to run.
In an aspect of the present invention, candidate locations in which each of the components is to be placed are assumed. Initially, all the cells on a printed circuit board are the candidates. The range of candidates for the location of each component is narrowed down (for example, the farthest cell from a fixed component is excluded from candidates for the location in which a component that directly relates to the fixed component is to be placed). An approximation problem is created from an original placement problem and a solution that optimizes the approximation problem is obtained. This solution is a feasible solution of the original placement problem as well. The process of narrowing down the candidates and solving the approximation problem is repeated until one candidate (or more than one candidate having an equal evaluation value) is found ultimately to determine the placement of the component.